import java.util.*;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class project {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> list=new ArrayList<>();
        int index1=0;
        int index2=0;
        int len1=firstList.length;
        int len2=secondList.length;
        while (index1<len1&&index2<len2){
            int x=Math.max(firstList[index1][0],secondList[index2][0]);
            int y=Math.min(firstList[index1][1],secondList[index2][1]);
            if(x<=y){
                list.add(new int[]{x,y});
            }
            if(firstList[index1][1]<secondList[index2][1]){
                index1++;
            }else{
                index2++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }





















    public int findClosest(String[] words, String word1, String word2) {
        int index=0;
        int len=words.length;
        int index1=-1;
        int index2=-1;
        int min=Integer.MAX_VALUE;
        while (index<len){
            String word=words[index];
            if(word.equals(word1)){
                index1=index;
                if(index2!=-1){
                    min=Math.min(min,index1-index2);
                }
            }else if(word.equals(word2)){
                index2=index;
                if(index1!=-1){
                    min=Math.min(min,index2-index1);
                }
            }
            index++;
        }
        return min;
    }



















    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        List<int[]> list=new ArrayList<>();
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                list.add(new int[]{arr[i],arr[j]});
            }
        }
        Collections.sort(list,(x,y)-> x[0]*y[1]-y[0]*x[1]);
        return list.get(k-1);
    }

















    public int minimumDeleteSum(String s1, String s2) {
        int row=s1.length();
        int col=s2.length();
        int[][] dp=new int[row+1][col+1];
        for(int i=1;i<=row;i++){
            dp[i][0]=dp[i-1][0]+s1.charAt(i-1);
        }
        for(int i=1;i<=col;i++){
            dp[0][i]=dp[0][i-1]+s2.charAt(i-1);
        }
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j]+s1.charAt(i-1),dp[i][j-1]+s2.charAt(j-1));
                }
            }
        }
        return dp[row][col];
    }


















    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> lists=new ArrayList<>();
        Queue<Node> queue=new ArrayDeque<>();
        if(root!=null){
            queue.add(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                List<Integer> list=new ArrayList<>();
                for(int i=0;i<size;i++){
                    Node node=queue.poll();
                    list.add(node.val);
                    for(Node value:node.children){
                        queue.add(value);
                    }
                }
                lists.add(list);
            }
        }
        return lists;
    }
}
